{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Transportation Problems\n", "## Basic Set up\n", "In the Introduction to MIP, we described the wide range of problems that can be modeled and solved with MIP, and described the setup of some widely used problem models. \n", "In this notebook, we introduce the transportation problem, as a special type of MIP problem particularly important for logistic operations. \n", "In the literature, the general transportation problem deals with the distribution of any commodity (generally goods) from a group of origins of the supply chain, or source facilities, called **sources** to the endpoints of the model of the supply chain, the receiving centers, called destinations. \n", "\n", "There are different types of goods or services that can be modeled with this model. Sources can be production centers, or warehouses. Destinations can be warehouse, demand regions or end customers, depending on the model. \n", "\n", "However, in the general problem formulation, we have $i \\in [1, ..., n]$ source nodes and $j \\in [1, ..., m]$ destination nodes. The objective is to minimize the overall costs of the distribution of goods at a minimum costs, subject to a set of constraints.\n", "\n", "Regarding the constraints, let us consider two types of constraints: \n", "\n", "- **supply constraints:** These constraints represent the limited capacity of the sources. For instance, production centers may have a limited production capacity, or source warehouses may have a limited storage capacity. Let us note $s_i$ the source capacity of source node $i$. \n", "\n", "- **demand constraints:** The demand constraints represent the distribution requirements at the destinations: what are the quantities of the goods required at each destination. Let us note as $d_j$ the demand of destination node $j$\n", "\n", "Now, based on this, let us define our set of decision variables as: \n", "\n", "- $x_{ij}$: (Integer) units to transport from source $i$ to destination $j$\n", "\n", "Assuming a distribution cost of $c_{ij}$ for each transported unit yields: \n", "\n", "$\\min z = \\sum_{i=1}^n{\\sum_{j=1}^m{c_{ij}*x_{ij}}}$\n", "\n", "$s.t$\n", "\n", "$\\sum_{j=1}^m{x_{ij}} \\leq s_i \\quad \\forall i$\n", "\n", "$\\sum_{i=1}^n{x_{ij}} \\geq d_j \\quad \\forall j$\n", "\n", "That is, the total number of units that leave a source cannot exceed the capacity of the source, and the total number of units that reach a destination must be at least equal to the demand. \n", "\n", "Note that the model has a feasible solution only if: \n", "\n", "$\\sum_{i=1}^n{s_i} \\geq \\sum_{j=1}^m{d_j}$\n", "\n", "That, is, the problem is only feasible if the overall capacity is sufficient to meet the overall demand.\n", "\n", "It is important to note that we may allow ourselves less slack by making any of the three inequalities above equalities. \n", "\n", " \n", "## Sourcing design\n", "In the basic set up above, it is assumed that it is possible to transport units from *any* source node to *any* destination. This implies that the design of the distribution network is known. But this may not be always the case. For instance, we may have different possible locations for source warehouse, each with different associated costs. In this case, our decision variables are not only the number of units to transport, but also determine from which subset of source nodes they must be transported. Thus, we can introduce a new set of decision variables: \n", "\n", "- $Y_i$: (Binary) determines whether units to any destination may be delivered from source node $i$\n", "\n", "We need to introduce new logical constraints to ensure that we do not deliver any units from source nodes that are not selected:\n", "\n", "$\\sum_{j=1}^m{x_{ij}} \\leq M*Y_i \\quad \\forall i$\n", "\n", "Where M is a large number. Since $Y_i$ is binary, this constraint forces that, in case that it is equal to zero, no units are sourced from source node $i$.\n", "\n", "This logical constraint can be merged with the source capacity constraint as: \n", "\n", "$\\sum_{j=1}^m{x_{ij}} \\leq s_i*Y_i \\quad \\forall i$\n", "\n", "This constraint takes into account the logical constraint and the capacity constraint. Since both constraint are equivalent, but the former is more restrictive and renders the first one irrelevant. \n", "\n", "We can now take into account in the objective function fixed costs that do not depend on the number of units. For instance, let us consider that the source warehouses have a fixed operation costs $f_i$. The problem in the basic set up becomes: \n", "\n", "$\\min z = \\sum_{i=1}^n{\\sum_{j=1}^m{c_{ij}*x_{ij}}} + \\sum_{i=1}^n{f_i*Y_i}$\n", "\n", "$s.t$\n", "\n", "$\\sum_{j=1}^m{x_{ij}} \\leq s_i*Y_i \\quad \\forall i$\n", "\n", "$\\sum_{i=1}^n{x_{ij}} \\geq d_j \\quad \\forall j$\n", "\n", "## Single source\n", "The single source constraint imposes that all the demand of a destination node is transported from the same origin. With this constraint, now the decision variables $x_{ij}$ become binary: \n", "\n", "- $X_{ij}$: (Binary) determines if source $i$ delivers all demand to destination $j$ {1 if yes, 0 otherwise}\n", "\n", "The demand constraint now becomes: \n", "\n", "$\\sum_{i=1}^n{d_j*X_{ij}} = d_j \\quad \\forall j$\n", "\n", "Note that we now multiply each binary decision variable times the demand of each destination. We have changed the type of the constraint from $\\geq$ to $=$ to avoid any slack. Although this change is optional, if not applied, the slack will be a multiple of the demand. Note that this is exactly the same requirement:\n", "\n", "$\\sum_{i=1}^n{X_{ij}} = 1 \\quad \\forall j$ \n", "\n", "We just divided by $d_j$ the right hand side and the left hand side.\n", "\n", "Also, we need to factor this into the objective function as: \n", "\n", "$\\min z = \\sum_{i=1}^n{\\sum_{j=1}^m{c_{ij}*d_j*X_{ij}}}$\n", "\n", "Since $X_{ij}$ is binary, and only equal to 1 for a destination node.\n", "\n", "## Network design\n", "In the set up above, we assume that the cost per unit from sources to destinations is fixed. In many cases however, this cost depends to a great extent on the design considerations taken in the distribution network between sources and destination. Similar to what we did with the sourcing design, we may be interested on evaluating the impact in the cost of the design of the distribution network, for instance, the location of intermediate nodes or *junctions* between the source nodes and destination nodes. In literature, this is known as the *transshipment problem* in the literature.\n", "Let us come back to the original problem, and assume that the source nodes are production plants, the destination nodes are retailer regions, and that we have intermediate warehouses that we can use to optimise costs. Let us assume that the production plants are fixed (i.e. the sourcing design is known), but that we can select a subset of warehouses from a set of candidate locations. \n", "\n", "First, let us modify the indices so that the distribution stages (from production plants through warehouses to regions) follow an alphabetical order: \n", "\n", "- $i$: Production plants $i \\in [1, ..., n]$\n", "- $j$: Possible warehouse locations $j \\in [1, ..., m]$ \n", "- $k$: Retailer regions $k \\in [1, ..., l]$\n", "\n", "Let us use the following notation for the coefficients of our problem: \n", "\n", "- $d_k$: yearly demand in retail region k\n", "- $a_{ij}$: cost of transporting 1 unit from plant i to warehouse j\n", "- $b_{jk}$: cost of transporting 1 unit from warehouse j to retailer region k\n", "- $F_{j}$: yearly operation costs of warehouse j\n", "- $c_i$: yearly production capacity of plant i\n", "\n", "Since we can decide the location of the warehouses, and the units to transport at each stage, the decision variables now become: \n", "\n", "- $Y_{j}$: (Binary) { 1 if a warehouse is placed in location j } {0 otherwise}\n", "- $s_{ij}$: integer units transported from plant i to warehouse j\n", "- $t_{jk}$: integer units transported from warehouse j to region k \n", "\n", "The objective function is to minimise costs: \n", "\n", "$\\min z = \\sum_{i=1}^{n}{\\sum_{j=1}^{m}{a_{ij}*s_{ij}}} + \\sum_{j=1}^{m}{\\sum_{k=1}^{l}{b_{jk}*t_{jk}}} + \\sum_{j=1}^{m}{F_j*Y_j}$\n", "\n", "Now, for the constraints, clearly, we need to satisfy all the constraints. The units sourced from each production plant cannot exceed the production capacity:\n", "\n", "$\\sum_{j=1}^{m}{s_{ij}} \\leq c_i \\quad \\forall i$\n", "\n", "We also need to ensure that the demand at each region is satisfied: \n", "\n", "$\\sum_{j=1}^{m}{t_{jk}} \\geq d_k \\quad \\forall k$\n", "\n", "Now, we need to ensure the material flow, that is, that the unit that leave a warehouse are not less than the units that enter the same warehouse:\n", "\n", "$\\sum_{i=1}^{n}{s_{ij}} \\geq \\sum_{k=1}^{l}{t_{jk}} \\quad \\forall j$\n", "\n", "And that a warehouse is built if it supplies to any region:\n", "\n", "$\\sum_{k=1}^{l}{t_{jk}} \\leq M*Y_j \\quad \\forall j$\n", " \n", "## Known variations\n", "### Combination of single-source in design constraints \n", "Any combinations of the variations above can be found in a problem instance. For instance, we might be interested in evaluating our network design with a single source constraint on intermediate nodes. Note that when we introduce a single source constraint in our problem, the decision variable that models the transport of units becomes binary. For instance, in the network design problem above, the decision variables Any combinations of the variations above can be found in a problem instance. For instance, we might be interested in evaluating our network design with a single source constraint on intermediate nodes. Note that when we introduce a single source constraint in our problem, the decision variable that models the transport of units becomes binary. For instance, in the network design problem above, the decision variables $t_{jk}$ become: \n", "\n", "- $T_{jk}$: (Binary) {1 units from warehouse j transported to region k, 0 otherwise}\n", " \n", "Since the variable are now binary, the single source constraint modifies the demand constraint, which now becomes: \n", "\n", "$\\sum_{j=1}^n{T_{jk}} = 1 \\quad \\forall k$ \n", "\n", "Now, since all $T_{jk}$ are binary, the logical constraint that rules the construction of warehouses can be written as: \n", "\n", "$T_{jk} \\leq Y_{j} \\quad \\forall j, \\forall k$\n", "\n", "### Other indices \n", "We may also introduce other indices in the problem, most common indices are: \n", "\n", "- **Type of product**: We can have different costs or demands depending on the type of product\n", "- **Periods**: The costs, or the demands can be dynamic and depend on a discrete time period, like the year, the month, or the day, so we might be interested in optimising the distribution network for a set of periods. \n", "\n", "When we introduce a new index into the model, the size of the problem (number of coefficients and decision variables) will grow accordingly. " ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.6" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 0 }